package 力扣.回溯;

//import com.sun.jmx.snmp.SnmpUnknownMsgProcModelException;

import java.util.*;

public class 子集II_90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace(nums,0,ans,box);
        return ans;
    }

    private void backTrace(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        int N = nums.length;
        ans.add(new ArrayList<>(box));
        if (i >= N){
            return;
        }
        Set<Integer> used = new HashSet<>();
        for (int j = i; j < N; j++) {
            int t = nums[j];
            if (!used.contains(t)){
                box.add(t);
                backTrace(nums, j + 1, ans, box);//跟i无关，递归j+1
                box.remove(box.size() - 1);
                used.add(t);
            }
        }
    }
    private void backTrace2(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        int N = nums.length;
        ans.add(new ArrayList<>(box));
        if (i >= N){
            return;
        }
//        int pre = Integer.MIN_VALUE;
        for (int j = i; j < N; j++) {
            int t = nums[j];
            if (j > i && nums[j] == nums[j -1 ])continue;

            box.add(t);
            backTrace2(nums, j + 1, ans, box);//跟i无关，递归j+1
            box.remove(box.size() - 1);
        }
    }
}
